﻿using System;
using System.Linq;
using Algoritmia.SemiRings;
using Algoritmia.StateSpaces;

namespace Algoritmia.Schemes.DynamicProgramming
{
    public class RecursiveDynamicProgrammingSolver<TState,TDecision,TResult,TWeight>
    {
        public TResult Solve(IBackwardsStateSpace<TState, TDecision> space, ISemiRing<TResult,TWeight> semiRing,
                             Func<TState, TDecision, TWeight> wfn )
        {
            Func<TState, TResult> solve = null;
            solve = s =>
                        {
                            var values =
                                space.IncomingDecisions(s).Select(
                                    d => semiRing.Times(solve(space.Undo(s, d)), wfn(s, d)));
                            var r = semiRing.Sum(values);
                            if (space.IsInitial(s))
                            {
                                r = semiRing.Plus(r, semiRing.One);
                            }
                            return r;
                        };
            return semiRing.Sum(space.FinalStates.Select(f => solve(f)));
        }
    }

    public class RecursiveDynamicProgrammingSolver<TState,TDecision,TResult>
        : RecursiveDynamicProgrammingSolver<TState,TDecision,TResult,TResult>
    {
    }
}
